package com.zlsy.learning.leetcode.arraycorrelation.array1365;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhouliang
 * @date 2020/6/8 20:16
 */
public class SmallerNumbersThanCurrent {

    /**
     * 自己想出的解法
     * 耗时严重，内存占用少
     */
    public static int[] smallerNumbersThanCurrent(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            map.put(i, nums[i]);
        }
        int[] newnums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int j = 0;
            int count = 0;
            while (j < nums.length) {
                if (i != j) {
                    Integer a = map.get(j);
                    if (num > a) {
                        count++;
                    }
                }
                j++;
            }
            newnums[i] = count;
        }
        return newnums;
    }

    /**
     * 没看懂......!
     * @param nums
     * @return
     */
    public static int[] smallerNumbersThanCurrent1(int[] nums) {
        int[] keg = new int[101];
        //遍历数组，统计这个传入的数组每个元素出现的次数
        for (int i : nums) {
            keg[i]++;
        }
        int pre = 0, next = 0;
        for (int i = 0; i < 101; i++) {
            int val = keg[i];
            if (keg[i] > 0) {
                keg[i] = pre;
            }
            pre += val;
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = keg[nums[i]];
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{8, 1, 2, 2, 3};
        int[] ints = smallerNumbersThanCurrent1(nums);
        System.out.println(ints);
    }
}
